package Heap.Medium;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class LC0347 {
    /**
     * 基于堆的做法，时间复杂度NlogN。如果堆的大小为K，那么时间复杂度可以降低到NlogK，符合进阶要求；这里不再实现。
     */
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> numFreqMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            numFreqMap.put(nums[i], numFreqMap.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<Integer> heap = new PriorityQueue<>((Integer i1, Integer i2) -> {
            return numFreqMap.get(i2) - numFreqMap.get(i1);
        });
        for (Map.Entry<Integer, Integer> pair : numFreqMap.entrySet()) {
            heap.add(pair.getKey());
        }

        int[] ret = new int[k];
        for (int i = 0; i < k; i++) ret[i] = heap.poll();
        return ret;
    }

    /**
     * 利用每个数字出现次数有限的性质，以出现次数为下标，将数字填入一个数组，然后倒序遍历即可。
     * 时间复杂度N。
     */
    public int[] topKFrequentOptimized(int[] nums, int k) {
        HashMap<Integer, Integer> numFreqMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            numFreqMap.put(nums[i], numFreqMap.getOrDefault(nums[i], 0) + 1);
        }
        ArrayList<ArrayList<Integer>> freqNumList = new ArrayList<>(nums.length + 1);
        for (int i = 0; i < nums.length + 1; i++) freqNumList.add(new ArrayList<>());
        for (Map.Entry<Integer, Integer> entry : numFreqMap.entrySet()) {
            freqNumList.get(entry.getValue()).add(entry.getKey());
        }
        int[] ret = new int[k];
        int count = 0;
        for (int i = nums.length; i >= 0; i--) {
            if (!freqNumList.get(i).isEmpty()) {
                ArrayList<Integer> list = freqNumList.get(i);
                for (int num : list) {
                    ret[count++] = num;
                    if (count >= k) return ret;
                }
            }
        }

        return ret;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 1, 1, 2, 2, 3};
        LC0347 solver = new LC0347();
        solver.topKFrequentOptimized(nums, 2);
    }
}
